SPOJ/SOLIT - 120. Solitaire/solit.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 int start[8][8], end[8][8], cur[8][8];
  28
  29 int di[] = {-1, +1, +0, +0};
  30 int dj[] = {+0, +0, -1, +1};
  31
  32 typedef unsigned long long int board;
  33
  34 #define outside(i, j) ((i) < 0 or (i) >= 8 or (j) < 0 or (j) >= 8)
  35
  36 board make_board(int b[8][8]){
  37     board ans = 0ULL;
  38     for (int i = 0; i < 8; ++i){
  39         for (int j = 0; j < 8; ++j){
  40             if (b[i][j]){
  41                 ans |= (1ULL << (i * 8 + j));
  42             }
  43         }
  44     }
  45     return ans;
  46 }
  47
  48 void unmake_board(board b, int out[8][8]){
  49     for (int i = 0; i < 8; ++i){
  50         for (int j = 0; j < 8; ++j){
  51             out[i][j] = 0;
  52         }
  53     }
  54     for (int i = 0; i < 8; ++i){
  55         for (int j = 0; j < 8; ++j){
  56             if (b & (1ULL << (i * 8 + j))){
  57                 out[i][j] = true;
  58             }
  59         }
  60     }
  61 }
  62
  63 void explore(board s, set<board> &seen) {
  64     queue<board> boards;
  65     queue<char> distance;
  66
  67     boards.push(s);
  68     distance.push(0);
  69
  70     while (boards.size() > 0) {
  71         board b = boards.front(); boards.pop();
  72         char d = distance.front(); distance.pop();
  73
  74         if (d == 4) continue; // Too far
  75
  76         unmake_board(b, cur);
  77
  78         //printf("d is %d\n", (int)d);
  79         //printf("cur is\n"); for (int i = 0; i < 8; ++i){ for (int j = 0; j < 8; ++j){ printf("%d ", cur[i][j]); } puts(""); } puts("");
  80
  81         for (int i = 0; i < 8; ++i){
  82             for (int j = 0; j < 8; ++j){
  83                 if (!cur[i][j]) continue;
  84                 for (int k = 0; k < 4; ++k){
  85                     int ni = i + di[k];
  86                     int nj = j + dj[k];
  87                     if (outside(ni, nj)) continue;
  88                     if (cur[ni][nj]){ //taken, let's move one extra cell
  89                         ni += di[k];
  90                         nj += dj[k];
  91                         if (outside(ni, nj)) continue;
  92                         if (cur[ni][nj]) continue;
  93                     }
  94                     assert(!cur[ni][nj]);
  95                     assert(cur[i][j]);
  96                     swap(cur[ni][nj], cur[i][j]);
  97
  98                     board cur_mask = make_board(cur);
  99                     if (seen.count(cur_mask) == 0){
 100                         // not seen, let's enqueue this new state
 101                         seen.insert(cur_mask);
 102                         boards.push(cur_mask);
 103                         distance.push(d + 1);
 104                     }
 105                     swap(cur[ni][nj], cur[i][j]);
 106                 }
 107             }
 108         }
 109     }
 110 }
 111
 112 int main(){
 113     int T;
 114     scanf("%d", &T);
 115     while (T--){
 116         for (int i = 0; i < 8; ++i){
 117             for (int j = 0; j < 8; ++j){
 118                 start[i][j] = end[i][j] = 0;
 119             }
 120         }
 121
 122         for (int i = 0; i < 4; ++i){
 123             int r, c;
 124             if (scanf("%d%d", &r, &c) != 2) return 0;
 125             r--, c--;
 126             assert(!start[r][c]);
 127             start[r][c]++;
 128         }
 129         for (int i = 0; i < 4; ++i){
 130             int r, c;
 131             if (scanf("%d%d", &r, &c) != 2) return 0;
 132             r--, c--;
 133             assert(!end[r][c]);
 134             end[r][c]++;
 135         }
 136
 137         set<board> s1;
 138         set<board> s2;
 139         s1.insert(make_board(start));
 140         s2.insert(make_board(end));
 141
 142         explore(make_board(start), s1);
 143         explore(make_board(end), s2);
 144
 145         //printf("s1.size = %d\n", s1.size());
 146
 147         bool ans = false;
 148         foreach(x, s1) {
 149             if (s2.count(*x) > 0){
 150                 ans = true;
 151                 break;
 152             }
 153         }
 154         puts(ans ? "YES" : "NO");
 155     }
 156     return 0;
 157 }